package com.mxw.算法之美.a5递归;

import java.util.HashMap;

/**
 * @author Administrator
 * @create 2024/7/18 11:40
 */
public class s1Recursion {

    /**
     * 递归满足的三个条件
     * 1.一个问题的解可以分解为几个子问题的解
     * 2.分解后的子问题，求解思路完全一样
     * 3.存在递归终止条件
     * <p>
     * 关键：写出递推公式，找到终止条件
     * 优点：表达力强，简洁
     * 缺点：空间复杂度高，堆栈溢出，重复计算，耗时
     */

    HashMap<Integer, Integer> memo = new HashMap<>();

    int f(int n) {
        // 终止条件
        if (n == 1) {
            return 1;
        }

        if (n == 2) {
            return 2;
        }
        // 优化：重复计算
        if (memo.containsKey(n)) {
            return memo.get(n);
        }
        // 递推公式
        int res = f(n - 1) + f(n - 2);
        memo.put(n, res);
        return res;
    }

    int f2(int n) {
        int res = 1;
        for (int i = 2; i <= n; i++) {
            res = res + 1;
        }
        return res;
    }
}
